Packet switching arrangements have proven to be preferred switching networks for many types of digital communication. Data packets each comprising a data portion and a numerical designation of a packet destination are applied to the inputs of such a network and the network conveys each packet to the identified destination.
The traffic to be conveyed by packet networks tends to be bursty. During some periods of time many packets arrive for distribution and at other times few packets arrive. For economic reasons packet networks for switching bursty traffic are engineered to convey an average rate of traffic rather than the maximum rate. Such networks include packet buffering before, within or on the outputs of the actual switch network to help average the traffic rates.
Buffering packets at the input to the network is advantageous since it permits the use of simple network architectures such as the sort-then-expand (also called Batcher-Banyan) networks. Known input buffering arrangements select packets from a plurality of parallel input buffers based on first-in-first-out rules or based on packet priorities. This results in the "blind" transmission of packets where packets are sent to the network without certainty that the packet destination will be available when the packet arrives. Such blind transmission results in wasted network resources and low network throughput since packets which cannot be used by busy destinations are transmitted to the network.
Studies have shown that the maximum throughput of networks which practice the blind transmission of packets is only approximately 59 percent (see for example M. J. Karol et. al. "Input versus Output Queuing on a Space Division Packet Switch", IEEE Global Communication Conference, Houston, 1986, page 659). Attempts have been made to reduce the impact of this low throughput by providing arrangements for the retransmission of blocked packets. Although slight improvements can be obtained from such impact reduction attempts they result in increased packet delays and more complex network architectures.
Centralized arrangements have been constructed to select packets for distribution based on destination availability. With such arrangements a single unit accumulates all incoming packets, or information about the destinations of all incoming packets, and selects packets based on the destination information of all accumulated packets and the availability of packet destinations. Given the total number of packets to be considered and the number of selections to be made, such centralized arrangements are slow compared to the packet rates of commercial high capacity distribution systems and limit their packet distribution rate.
A need exists in the art for packet selection arrangements which provide the throughput advantages of packet selection based on destination availability while operating at high packet rates compatible with commercial high capacity packet systems.